package week1.undirected;

import edu.princeton.cs.introcs.In;
import edu.princeton.cs.introcs.StdOut;
import graph.impl.StringGraph;
import graph.impl.StringGraphDFS;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class CC {
	private Map<String,Boolean> visited = null;
	private StringGraph graph = null;
	private Map<String,Integer> connectedMap = null;
	private int connectedcount = 0;
	
	public CC(StringGraph graph) {
		this.graph = graph;
		visited = new HashMap<String, Boolean>();
		connectedMap = new HashMap<String, Integer>();		
	}
	public void dfs(String sourceVertex){
		Set<String> edges = graph.getEdges(sourceVertex);
		this.visited.put(sourceVertex, Boolean.TRUE);
		this.connectedMap.put(sourceVertex, this.connectedcount);
		System.out.print(sourceVertex +" ");
		for(String edge : edges){
			if(visited.get(edge) == null){
				dfs(edge);
			}
		}
	}
	public static void main(String[] args) {
		In in = new In(args[0]);
		StringGraph stringGraph = new StringGraph(in);
		CC dfs = new CC(stringGraph);
		Set<String> vertexSet = dfs.graph.getVertices();
		List<String> vertexList = new ArrayList<String>(vertexSet);
		Collections.sort(vertexList);		
		for(String vertex : vertexList){
			if(!dfs.visited.containsKey(vertex)){
				dfs.dfs(vertex);
				dfs.connectedcount++;
			}			
		}
		System.out.println();
		for(String vertex : vertexList){
			System.out.print(vertex + " " );
		}
		System.out.println();		
		
		for(String vertex : vertexList){
			System.out.print(dfs.connectedMap.get(vertex) + " ");
		}
//		if(dfs.visited.size() == stringGraph.vertexCount) {
//			StdOut.println(dfs.visited);
//		}
	}

}
